package com.dataStructure.sort;

import java.util.Arrays;
import java.util.PriorityQueue;

public class MergeSort {

    public void sort(int[] nums, int left, int right) {
        if (left == right) {
            return;
        }
        int mid = (left + right) /2;

        sort(nums, left, mid);
        sort(nums, mid + 1, right);

        merge(nums, left, mid, right);

    }

    private void merge(int[] nums, int left, int mid, int right) {

        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int index = 0;
        while (i <= mid && j <= right) {
            if (nums[i] > nums[j]) {
                temp[index] = nums[j];
                j++;
            } else {
                temp[index] = nums[i];
                i ++;
            }
            index ++;
        }

        while (i <=mid) {
            temp[index] = nums[i];
            index++;
            i++;
        }
        while(j <= right) {
            temp[index] = nums[j];
            index++;
            j++;
        }

        for (int z = 0; z < temp.length; z++) {
            nums[left] = temp[z];
            left++;

        }

    }
}
class Test {
    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] ints = {4, 5, 1, 7, 8};
        mergeSort.sort(ints, 0, ints.length -1);
        System.out.println(Arrays.toString(ints));

        PriorityQueue<Integer> queue = new PriorityQueue<>();
        queue.add(1);
        queue.poll();
    }
}
